#define _CRT_SECURE_NO_WARNINGS  1
//一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
//一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//删除链表元素

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL, * tail = NULL;
    while (cur)
    {
        if (cur->val == val)
        {
            //删除
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
        else {
            //尾差
            if (tail == NULL)
            {
                newhead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }

    }
    if (tail)
    {
        tail->next = NULL;
    }
    return newhead;

}
//反转单链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1, * n2, * n3;
    n1 = NULL;
    n2 = head;
    if (n2)
    {
        n3 = n2->next;
    }
    while (n2)
    {
        if (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
        }
        if (n3)
        {
            n3 = n3->next;
        }
    }
    return n1;
}
//给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //方法：快慢指针
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
//输入一个链表，输出该链表中倒数第k个结点
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

 /**
  *
  * @param pListHead ListNode类
  * @param k int整型
  * @return ListNode类
  */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    struct ListNode* slow = pListHead;
    struct ListNode* fast = pListHead;
    while (k--)
    {
        if (fast == NULL)
            return NULL;
        fast = fast->next;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;

}
//将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //判断list1 listen 为空时
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            if (tail == NULL)
            {
                head = tail = list1;
            }
            else {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }
        else {
            if (tail == NULL)
            {
                head = tail = list2;
            }
            else {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if (list1)
    {
        tail->next = list1;
    }
    if (list2)
    {
        tail->next = list2;
    }
    return head;
}
//链表的回文结构
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        //找中间节点slow
        struct ListNode* slow = A;
        struct ListNode* fast = A;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        //反转链表
        struct ListNode* head = slow;
        struct ListNode* n1, * n2, * n3;
        n2 = head;
        n1 = NULL;
        if (n2)
        {
            n3 = n2->next;
        }
        while (n2)
        {
            if (n2)
            {
                n2->next = n1;
                n1 = n2;
                n2 = n3;
            }
            if (n3)
            {
                n3 = n3->next;
            }
        }
        struct ListNode* tail = n1;
        //对比
        struct ListNode* head1 = A;
        while (tail != slow)
        {
            if (head1->val != tail->val)
            {
                return false;
            }
            tail = tail->next;
            head1 = head1->next;
        }
        return true;
    }
};